COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\rm
C00007 ENDMK
C⊗;
\rm
\magnification=\magstephalf

\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}

\line{\sevenrm A48.tex[106,rwf] \today\hfill}

\vskip .25in

\noindent
Proofs from Algorithms

\vskip .125in

Some mathematical results assert the existence of numbers (say) with specific
relations to other numbers. Often the best way to prove such a result is to
design an algorithm and, with it, a proof that the algorithm produces a
result with the desired properties. To illustrate this, we show that all the
divisors of a set of numbers divide the greatest common divisor. In the
proof that follows, all numbers are assumed to be non-negative integers.

\vskip .125in

\noindent
Definition: We say $d$ is a divisor of $x$ if $x/d=q$ is an integer, i.e., if
$d\cdot q=x$ for some integer $q$. Because $1\cdot x=x\cdot 1=x$,
the divisors of $x$ always include
$x$ and 1. If $x>0$, then no divisor of $x$ is greater than $x$; if $d$
were a divisor
of $x$ larger than $x$, we would have $d\cdot 0<x$, $d\cdot 1>x$, and there are no 
values of $q$ between 0 and 1.

\vskip .125in

\noindent
Drill: Show zero divides only zero, and every number divides zero.

Every non-empty set of numbers $X=\lbrace x↓1, x↓2,\ldots ,x↓n\rbrace$ 
has at least one common
divisor that divides all its members, namely 1. Unless $X=\lbrace 0\rbrace$, 
no common
divisor of $X$ can be larger than the largest member of $X$, so $X$ must have a
largest common divisor.

Let $D(X)$ be the set of divisors of $X$. If $E$ is another set 
$\lbrace y↓1, y↓2,...y↓n\rbrace$,
and if each $y↓i$ is a linear combination $\pm a↓1x↓1\pm a↓2x↓2\pm\cdots\pm a↓nx↓n$,
then any $d\in D(X)$ also divides each $y↓i$, and $d\in D(Y)$.

In particular, if $X=\lbrace x↓1,x↓2,\ldots , x↓n\rbrace$, and
$Y=\lbrace x↓1,x↓2,\ldots , x↓{i-1}, x↓i-x↓j, x↓{i+1},\ldots , x↓n\rbrace$,
$i\not=j$, the $D(X)\subseteq D(Y)$ and $D(Y)\subseteq D(X)$, so $D(Y)=D(X)$,
because $x↓i-x↓j=+1\cdot x↓i-1\cdot x↓j$ and $x↓i=+1\cdot (x↓i-x↓j)+1\cdot x↓j$.

If $X\not=\lbrace 0\rbrace$, $D(X)=D(X-\lbrace 0\rbrace )$. Adopting the
convention $D(0)={\bf N}, D(X)=D(X-\lbrace 0\rbrace )$ for all $X$, 
so we assume zeroes are always omitted from X.

Starting with any set $X$, we can construct a sequence
$X↓0, X↓1, X↓2,\ldots , X↓p$ where $X↓0=X$ and $D(X↓k)=D(X↓{k+1})$, replacing
the largest $x↓i$ in $x↓k$ by $x↓i-x↓j$, where $0<x↓j<x↓i$, until
$\mid X↓p\mid ≤1$. Because $\sum ↓{x↓i\in X↓k}x↓i$ decreases as $k$ increases,
the sequence must end, with $\mid X↓p\mid ≤1$, $X↓p=\lbrace g\rbrace$, and
$D(\lbrace x↓1, x↓2, \ldots , x↓n\rbrace )=D(\lbrace g\rbrace )$.
The largest divisor of $g$ is $g$ itself, so a number is a common divisor
of $X$ if and only if it divides $g$, and $g$ is the largest common divisor
of $X$. By giving an algorithm to find it, and proving its properties as we
went along, we have shown that every common divisor of a set divides its
greatest common divisor.

\vfil\end